// bzoj1532
// 题意：已知n(<=10000)个人，有m(<=10000)场比赛，两个人之前可以重复多场
//       比赛，问赢的最多场的人的最小赢的场数是多少。
//
// 题解：其实不难，二分答案ans，然后网络流。
//       将m场比赛都建点，每场比赛两个人都连向这场比赛，原点连向每个人
//       容量为ans，然后跑一遍最大流，如果最大流为m就可行。
//
//       令人想不通的是这个复杂度。dinic的话如果是unit capacities复杂度
//       有个更紧的上届O(min{V^(2/3), E^(1/2)})。
//       但是这道题也不全是unit capacities，不过unit capacity的边到是挺
//       多的...
// 
// run: $exec < input
#include <cstdio>
#include <vector>
#include <limits>
#include <queue>

template <class T>
struct dinic
{
	typedef T value_type;
	typedef int size_type;
	typedef std::vector<size_type>::iterator edge_iter;

	struct edge {
		size_type from, to;
		value_type capacity, flow;
	};

	dinic(size_type num) : size(num)
	{
		graph.resize(num);	//[0, num)
		dist.resize(num);	//[0, num)
	}

	void add_edge(int u, int v, value_type cap = capacity_inf)
	{
		edge tmp;
		tmp.from = u; tmp.to = v; tmp.capacity = cap; tmp.flow = 0;
		edges.push_back(tmp);
		graph[u].push_back(edges.size() - 1);

		tmp.from = v; tmp.to = u; tmp.capacity = 0; tmp.flow = 0;
		edges.push_back(tmp);
		graph[v].push_back(edges.size() - 1);
	}

	bool bfs_label(size_type source, size_type target)
	{
		std::fill(dist.begin(), dist.end(), -1);
		std::queue<size_type> q;
		q.push(source);
		dist[source] = 0;
		while (!q.empty()) {
			size_type now = q.front();
			q.pop();
			for (edge_iter it = graph[now].begin(); it != graph[now].end(); ++it) {
				edge e = edges[*it];
				if (dist[e.to] == -1 && e.capacity > e.flow) {
					q.push(e.to);
					dist[e.to] = dist[now] + 1;
				}
			}
		}
		return dist[target] != -1;
	}

	value_type dfs(size_type v, size_type target, value_type f)
	{
		if (v == target || !f) return f;
		value_type block_flow = 0;
		for (edge_iter it = graph[v].begin(); it != graph[v].end(); ++it) {
			edge & e = edges[*it];
			if (e.capacity > e.flow && dist[e.to] == dist[v] + 1) {
				value_type tmp = dfs(e.to, target,
						std::min(e.capacity - e.flow, f - block_flow));
				block_flow += tmp;
				e.flow += tmp;
				edges[(*it) ^ 1].flow -= tmp;
			}
		}
		if (!block_flow) dist[v] = -1;
		return block_flow;
	}

	value_type max_flow(size_type source, size_type target)
	{
		value_type flow = 0;
		for (int tmp; bfs_label(source, target); )
			while ((tmp = dfs(source, target, capacity_inf))) flow += tmp;
		return flow;
	}

//private:
	value_type static const capacity_inf = 1 << 30;
	size_type size;
	std::vector<int> dist;
	std::vector<edge> edges;
	std::vector<std::vector<size_type> > graph;
};

int const maxn = 10007;
int head[maxn], end_point[maxn * 2], next[maxn * 2];
int alloc = 2;
int n, m;

void add_edge(int u, int v)
{
	end_point[alloc] = v; next[alloc] = head[u]; head[u] = alloc++;
	end_point[alloc] = u; next[alloc] = head[v]; head[v] = alloc++;
}

bool judge(int x)
{
	int s = 0, t = n + m + 1;
	dinic<int> d(t + 1);
	for (int i = 1; i <= n; i++)
		d.add_edge(s, i, x);
	for (int i = 1; i <= m; i++) {
		int u = end_point[i * 2];
		int v = end_point[i * 2 + 1];
		d.add_edge(u, n + i, 1);
		d.add_edge(v, n + i, 1);
		d.add_edge(n + i, t, 1);
	}
	return d.max_flow(s, t) == m;
}

int main()
{
	std::scanf("%d%d", &n, &m);
	if (!m) { std::printf("0\n"); return 0; }
	for (int i = 0, x, y; i < m; i++) {
		std::scanf("%d%d", &x, &y);
		add_edge(x, y);
	}
	int l = 1, r = m;
	while (l + 1 < r) {
		int mid = (l + r) / 2;
		if (judge(mid)) r = mid;
		else l = mid;
	}
	if (judge(l)) r = l;
	std::printf("%d\n", r);
}

